#include <stdio.h>
int f[1000001];
int main ()
{
    int i, n;
    scanf("%d", &n);
    f[0] = f[1] = 1;
    for (i=2; i<=n; ++i) 
	{
        if (i % 2)
            f[i] = f[i-1];
        else
            f[i] = (f[i-1] + f[i/2]) % 1000000000;
    }
    printf ("%d\n", f[n]);
    return 0;
}